package leetcode.hot100;

import java.util.Scanner;
import java.util.Stack;

public class Solution85 {

    public static void main(String[] args) {
        char[][] matrix = {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
        System.out.println(new Solution85().maximalRectangle(matrix));
    }

    public int maximalRectangle(char[][] matrix) {
        //对每一行计算竖直方向上连续的1的个数，这就是柱子的高度，用下面的函数求得最大面积
        //对每一行求最大面积，最终的最大面积就是这些面积的最大
        if(matrix.length==0) return 0;
        int[] height = new int[matrix[0].length]; //每一行的连续1高度
        int maxArea = 0, curArea;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < height.length; j++) {
                if(matrix[i][j]=='1') height[j]++;
                else height[j] = 0;
            }
            curArea = largestRectangleArea(height);
            maxArea = maxArea>curArea?maxArea:curArea;
        }
        return maxArea;
    }

    public int largestRectangleArea(int[] heights) {
        int res = 0, len = heights.length;
        //为了便于计算，在原数组两头各补一个0作为“哨兵”
        int[] newHeights = new int[len+2];
        System.arraycopy(heights,0,newHeights,1,len);
        len += 2;
        heights = newHeights;

        //使用一个单调栈存放单调元素下标,当栈为空或者要入栈的元素不小于栈顶，直接入栈
        //当要入栈元素大于栈顶，将栈中比当前元素小的都出栈，再将当前元素入栈
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for(int i=1;i<len;i++){
            while(heights[i]<heights[stack.peek()]){
                int curHeight = heights[stack.pop()];
                //有可能此时前面还有很多和当前高度一样的，将他们统统出栈，减少无用的计算
                while(curHeight==heights[stack.peek()]) stack.pop();
                //计算面积
                int curWidth = i-stack.peek()-1;
                res = Math.max(res,curHeight*curWidth);
            }
            stack.push(i);
        }
        return res;
    }
}
